package Dynamic_programming;

import org.junit.Test;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.text.DecimalFormat;
import java.time.LocalDateTime;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @Description: 算法$
 * @Param: $
 * @return: $
 * @Author 万家欣
 * @Date: 2022/6/6
 * Algorithm
 * @Version 1.0
 */
public class MyCalendarThree {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int l = getDeep(root.left);
        int r = getDeep(root.right);
        return Math.abs(l - r) < 2;
    }

    private int getDeep(TreeNode left) {
        if(left == null){
            return 0;
        }
        int l = getDeep(left.left) + 1;
        int r = getDeep( left.right) + 1;
        return Math.abs(l - r) < 2 ? Math.max(l,r):Integer.MAX_VALUE;
    }
    public boolean repeatedSubstringPattern(String s) {
        if(s ==null || s.length() <= 1){
            return false;
        }
        for (int i = 1; i < s.length() - 1; i++) {
            String x = s.substring(0,i);
            if(s.replace(x,"").equals("")){
                return true;
            }
        }
        return false;
    }
    @Test
    public void t(){
       /* String[] x =new String[]{"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
        System.out.println(evalRPN(x));*/
       // plusOne(new int[]{9,9});
        DecimalFormat df = new DecimalFormat("#.00");
        double d = 0.23565;
        System.out.println(df.format(d));
    }
    public int evalRPN(String[] tokens) {
        Stack<Integer> num = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if(!(tokens[i].equals("+")||tokens[i].equals("-")||tokens[i].equals("*")||tokens[i].equals("/"))){
                num.push(Integer.parseInt(tokens[i]));
            }else {
                int b = num.pop();
                int a = num.pop();
                if (tokens[i].equals("+")) {
                    num.push((a + b));
                } else if (tokens[i].equals("-")) {
                    num.push((a - b));
                } else if (tokens[i].equals("*")) {
                    num.push((a * b));
                } else if (tokens[i].equals("/")) {
                    num.push((a / b));
                }
            }
        }
        return num.pop();
    }
    public int[] plusOne(int[] digits) {
        int n = digits.length - 1;
        digits[n] += 1;
        int temp = (digits[n]) / 10;
        digits[n] %= 10;
        int i = n - 1;
        while (temp > 0 && i >= 0){
            digits[i] += 1;
            temp = (digits[i]) / 10;
            digits[i] %= 10;
            i -- ;
        }
        int[] res;
        if(temp > 0){
            res = new int[digits.length + 1];
            res[0] = 1;
            for (int j = 0; j < digits.length; j++) {
                res[j + 1] = digits[j];
            }
        }else {
            res = digits;
        }
        return res;
    }
    public boolean isBoomerang(int[][] points) {
        return (points[0][0] - points[1][0])*(points[1][1]-points[2][1]) != (points[1][0] - points[2][0]) * (points[0][1] - points[1][1]);
    }
    class Foo {
          volatile int x;
        public Foo() {
            x = 3;
        }

        public void first(Runnable printFirst) throws InterruptedException {
                while (x != 3) {

                }
                    // printFirst.run() outputs "first". Do not change or remove this line.
                    printFirst.run();
                    x--;
        }

        public void second(Runnable printSecond) throws InterruptedException {
            while (x != 2) {

            }
                // printSecond.run() outputs "second". Do not change or remove this line.
                printSecond.run();
                x--;

        }

        public void third(Runnable printThird) throws InterruptedException {
            while (x != 1) {
            }
                // printThird.run() outputs "third". Do not change or remove this line.
                printThird.run();
                x = 3;

        }
    }
    int[][] t ;
    int [] sum;
    int n;
    Random random = new Random();
    public void Solution(int[][] rects) {
    t = rects;
    n = rects.length;
    sum = new int[n + 1];
        for (int i = 1; i <= rects.length; i++) {
            sum[i] = sum[i - 1] + (rects[i - 1][2] - rects[i - 1][0] + 1)*(rects[i - 1][3] - rects[i - 1][1] + 1);
        }
    }

    public int[] pick() {
        int val = random.nextInt(sum[n]) + 1;
        int l = 0,r = n;
        while (l < r){
            int mid = l + r>>1;
            if(sum[mid] >= val){
                r = mid;
            }else {
                l = mid+1;
            }
        }
        int[] cur = t[r - 1];
        int x = random.nextInt(cur[2] - cur[0] + 1)  +cur[0];
        int y = random.nextInt(cur[3] - cur[1] + 1)  +cur[1];
        return new int[]{x,y};
    }
    public int countPalindromicSubsequences(String s) {
        final int MOD = 1000000007;
        int n = s.length();
        int[][][] dp = new int[4][n][n];
        for (int i = 0; i < n; i++) {
            dp[s.charAt(i) - 'a'][i][i] = 1;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                for (char c = 'a'; c <= 'd'; c++) {
                    int k = c - 'a';
                    if (s.charAt(i) == c && s.charAt(j) == c) {
                        dp[k][i][j] = (2 + (dp[0][i + 1][j - 1] + dp[1][i + 1][j - 1]) % MOD + (dp[2][i + 1][j - 1] + dp[3][i + 1][j - 1]) % MOD) % MOD;
                    } else if (s.charAt(i) == c) {
                        dp[k][i][j] = dp[k][i][j - 1];
                    } else if (s.charAt(j) == c) {
                        dp[k][i][j] = dp[k][i + 1][j];
                    } else {
                        dp[k][i][j] = dp[k][i + 1][j - 1];
                    }
                }
            }
        }

        int res = 0;
        for (int i = 0; i < 4; i++) {
            res = (res + dp[i][0][n - 1]) % MOD;
        }
        return res;
    }
    //给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数 。
    public int consecutiveNumbersSum(int n) {
   /* //创建前缀和数组：(时间复杂度过高，放弃）
        int[] ints = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            ints[i] = ints[i - 1] + i;
        }
        //通过便利来进行循环长度从1 到 n
        int sum = 0;
        for (int i = 1; i <= n ; i++) {
            for (int j = i; j < ints.length ; j++) {
                if(ints[j] - ints[j - i] == n){
                    sum++;
                }
            }
        }
        return sum;*/
        //解析：由题和等差数列求和(（a + an） * k)/2 = n -->an = a + k - 1;-->2a = (2n)/k - k + 1;
        //因为a > 0 并且 k > 0, n > 0；所以（2n)/k - k + 1 = 2a >= 2; -->（2n)/k - k > 0; --> 2n > k*k;
        //因此有k的取值范围：（1，根号2n）
         n = n *2;
        int sum = 0;
        //以i为k进行遍历：
        for (int i = 1; i* i <= n  ; i++) {
            //由2n > k*k 并且n，k都为正整数得n %k必然为正整数
            if(n % i != 0 ) continue;
            //判断是否能够求出对应的a满足条件
                if(((n / i) - i + 1) % 2 == 0){
                    sum ++;
                }
        }
        return sum;
    }
@Test
public void  p(){
        TreeNode t = new TreeNode(1,new TreeNode(2,new TreeNode(4,null,null),null),new TreeNode(3,new TreeNode(5,new TreeNode(7,null,null),null),new TreeNode(6,null,null)));
    System.out.println(largestValues(t));

    }

    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int val = root.val;
        queue.add(root);
       while (!queue.isEmpty()){
           int size = queue.size();
           for (int i = 0; i < size; i++) {
               TreeNode t = queue.poll();
               if(i == 0){
                   val = t.val;
               }
               if(t.left !=null){
                   queue.add(t.left);
               }
               if(t.right != null){
                   queue.add(t.right);
               }
           }
       }
       return val;
    }

    private static final String fileName = "D:\\Algorithm\\src\\main\\java\\Dynamic_programming\\response.txt";

    public static void main(String[] args) {

        //读取文件
        BufferedReader br = null;
        StringBuffer sb = null;
        try {
            br = new BufferedReader(new InputStreamReader(new FileInputStream(fileName), "UTF-8")); //这里可以控制编码
            sb = new StringBuffer();
            String line = null;
            int index = 0;
            while ((line = br.readLine()) != null) {
            index ++;
            if(index >=7){

            }
                sb.append(line);
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                br.close();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String s = new String(sb); //StringBuffer ==> String
        System.out.println("addressBook.txt内容为==> " + s);
        System.out.println(    );
        //1、匹配子串
        String regex = "1[378][0-9]{9}";

        //2、获取匹配器
        Pattern p = Pattern.compile(regex);
        Matcher m = p.matcher(s);

        //3、使用匹配器的group()方法来获取:（find方法是判断是否具有匹配子串）、
        System.out.println("”" + s + "符合要求的电话号码有：");
        while (m.find()) {
            System.out.println(m.group());
        }

    }


    HashMap<Integer,Integer> value = new HashMap<>();
    public int[] findFrequentTreeSum(TreeNode root) {
        if(root == null){
            return new int[]{};
        }

        int v = getvalue(root);
        int x=  value.getOrDefault(v,0);
        value.put(v,x+1);
        List<Integer> list = new ArrayList<>();
        int max =Integer.MIN_VALUE;
        for (Integer integer:value.keySet()) {
            int times = value.get(integer);
            if(times > max){
                list.clear();
                list.add(integer);
                max = times;
            }else if(times == max){
                list.add(integer);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private int getvalue(TreeNode root) {
        if(root ==null){
            return 0;
        }
        int v = root.val;
       if(root.left != null){
           int l  = getvalue(root.left);
         int x=  value.getOrDefault(l,0);
         value.put(l,x+1);
         v+=l;
       }
       if(root.right != null){
           int r = getvalue(root.right);
           int y = value.getOrDefault(r,0);
           value.put(r,y + 1);
           v+=r;
       }
       return v;
    }

    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < size ; i++) {
                TreeNode temp = queue.poll();
                if(max < temp.val){
                    max = temp.val;
                }
                if(temp.left != null){
                    queue.add(temp.left);
                }
                if(temp.right != null){
                    queue.add(temp.right);
                }
            }
            res.add(max);
        }
        return res;
    }
    public Node insert(Node head, int insertVal) {
        if(head == null){
            Node res = new Node(insertVal);
            res.next = res;
            return res;
        }
        Node pre = head;
        Node next = head.next;
        boolean f = false;
        while (next != head){
            //环形链表的最大和最小点的交接处：
            if(pre.val > next.val){
                if(pre.val < insertVal || next.val > insertVal){
                    Node t = new Node(insertVal);
                    pre.next = t;
                    t.next = next;
                    break;
                }
            }else {
                if(pre.val <= insertVal && next.val >= insertVal){
                    Node t = new Node(insertVal);
                    pre.next = t;
                    t.next = next;
                    break;
                }
            }
            pre = next;
            next = next.next;
        }
        return head;

    }

    public void duplicateZeros(int[] arr) {
        int next =0,cur = arr[0];
        for (int i = 0; i < arr.length && next < arr.length; i++) {
            if(arr[i] == 0){
                //找到第一个下标不为0的元素
                while (next < arr.length && arr[next] == 0 ){
                    next ++;
                }
                if(next >= arr.length ){
                    break;
                }
                //交换数据
                cur = arr[next];
                int index = next + 1;
                while (index < arr.length){
                    int t = cur;
                    cur = arr[index];
                    arr[index] = t;
                }
            }
        }
    }

    public void wiggleSort(int[] nums) {
        
    }
}
